package _dp_base;

import java.util.Arrays;

/**
 * 2466. 统计构造好字符串的方案数
 */
public class No2466 {
    private int low, high, zero, one;
    private int[] cache;
    private final int MOD = (int) Math.pow(10, 9) + 7;

    /**
     * 0. 正向逻辑（会超时）
     */
    public int countGoodStrings0(int low, int high, int zero, int one) {
        this.low = low;
        this.high = high;
        this.zero = zero;
        this.one = one;
        cache = new int[high + 1];
        Arrays.fill(cache, -1);
        return dfs0(0) % MOD;
    }

    private int dfs0(int i) {
        if (i > high) return 0;
        else if (cache[i] != -1) return cache[i];
        else if (i < low) return cache[i] = dfs0(i + zero) + dfs0(i + one);
        else return cache[i] = dfs0(i + zero) + dfs0(i + one) + 1;
    }

    /**
     * 1. 递归
     */
    public int countGoodStrings1(int low, int high, int zero, int one) {
        this.zero = zero;
        this.one = one;
        cache = new int[high + 1];
        Arrays.fill(cache, -1);
        cache[0] = 1;
        int answer = 0;
        for (int i = low; i <= high; i++) {
            answer += dfs(i);
            answer = answer % MOD;
        }
        return answer % MOD;
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        else if (cache[i] != -1) return cache[i];
        else return cache[i] = (dfs(i - zero) + dfs(i - one)) % MOD;
    }

//    /**
//     * 2. 迭代 TODO 逻辑有误，懒得改了，啥时候有机会再改
//     */
//    public int countGoodStrings2(int low, int high, int zero, int one) {
//        int[] f = new int[high + 1];
//        f[0] = 1;
//        for (int i = Math.min(zero, one); i < high; i++) {
//            f[i] = (f[Math.max(i - zero, 0)] + f[Math.max(i - one, 0)]) % MOD;
//        }
//        int answer = 0;
//        for (int i = low; i <= high; i++) {
//            answer += f[i];
//            answer = answer % MOD;
//        }
//        return answer % MOD;
//    }
}
